1. Field of the Invention
The present invention relates the scheduling of performance requests in video-on-demand systems.
2. Related Art
In Video-On-Demand (VOD) systems, there are often hot videos (i.e. movies or other programs) which are requested by many viewers. Batching (letting viewers requesting the same video to share a single video stream) is often used to increase the system throughput.
Depending upon the system load, a video request may not get started immediately. While viewers can usually tolerate and accept a small delay (say 3-5 minutes), longer delays will typically cause some viewers to be turned away (i.e. leave the system after making or request or not even make the request at all). The likelihood that viewers will be turned away increases with the length of delay.
The conventional approach to video scheduling is the first-come-first-served (FCFS) policy. Under this policy, all video requests join a single request queue. Once a stream capacity becomes available, the request at the front of the queue is served. To support hatching, all subsequent requests on the same video are also served by this stream.
An alternative is to maintain a separate request queue for each video and select the video with the longest queue for the next showing. This is referred to as the longest queue length first (LQF) policy. Still another approach is to provide periodic showing (say every 5 minutes) for the hottest video. For other requests not covered by the periodic showing, another scheduling scheme such as FCFS can be used.
As mentioned before, waiting requests may depart from the queue if the waiting time exceeds the tolerance of the requesting viewers. This loss of viewers (sometimes referred to as reneging) is undesirable. The choice of video scheduling policy can have a significant effect on the amount of batching and viewer losses. The FCFS policy does not take into account the batching factor while the LQF policy ignores the wait time already incurred by the waiting requests. Periodic showing (when used alone) does not provide the flexibility needed to cope with dynamic load variations.